/*
题目: 规划兼职工作
你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。

给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

注意，时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

https://leetcode.cn/problems/maximum-profit-in-job-scheduling
 */
public class JobScheduling {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        // 将三个信息合并在一起
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i ++) {
            jobs[i][0] = startTime[i];
            jobs[i][1] = endTime[i];
            jobs[i][2] = profit[i];
        }

        // 根据 结束时间 升序, 根据 结束时间 这一列排序
        Arrays.sort(jobs, (int[] o1, int[] o2) -> {return o1[1] - o2[1];});
        // 对于前 i 份兼职来说的最大利润
        int[] dp = new int[n];
        // 前 0 份的最大收益
        dp[0] = jobs[0][2];

        for (int i = 1; i < n; i ++) {
            // 对于每一份工作, 可以选 也可以 不选
            // 找出第一个结束时间 小于 当前开始时间的 兼职
            int k = get(jobs, i - 1, jobs[i][0]);
            // 如果能查找到 第一个结束时间 小于 当前兼职开始时间, 那就需要考虑
            if (k >= 0)
                //                不选         选这个兼职
                dp[i] = Math.max(dp[i - 1], jobs[i][2] + dp[k]);

                // 如果找不到, 那就考虑放弃这个兼职, 还是只拿这个兼职
            else
                dp[i] = Math.max(dp[i - 1], jobs[i][2]);
        }

        return dp[n - 1];
    }

    // 找出第一个 jobs[i][1] 小于等于 v 的下标
    private int get(int[][] jobs, int right, int v) {
        int left = 0;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (jobs[mid][1] <= v) {
                left = mid + 1;
            } else { // 否则
                right = mid - 1;
            }
        }
        return left - 1;
    }
}
